Pipelining is a well-understood implementation technique whereby multiple instructions are overlapped in execution to increase the processing speed of a throughput-oriented computer system. Pipelines within a computer resemble an assembly line in that each portion of the pipeline (commonly referred to as "pipestages") completes a portion of the instruction's execution. Instructions enter one end of the pipeline and exit the other end--with the time required for moving an instruction one pipestage down the assembly line being known as a machine cycle.
Some modern computer systems employ what is known as "superpipelining". Superpipelined machines have higher clock rates and deeper pipelines and are characterized by pipelining of most functional units. Superpipelining refers to taking a function that is currently performed in, say, one pipestage, and spreading it over two or more pipestages. In general, the purpose of increasing the number of pipestages in a superpipelined machine is to produce a shorter clock cycle.
Today, processors are commercially available which superpipeline memory operation units such as cache memories. Superpipelining of actual arithmetic units, however, has yet to be successfully achieved. While academicians have proposed designs for superpipelining arithmetic units, these proposals suffer from serious drawbacks.
For example, many proposed superpipelined arithmetic units for computer systems suffer poor performance because the result of an arithmetic operation is often used immediately when it is ready or available. Very often there is a need to use the results of a computation soon afterwards, e.g., one instruction later. If it takes two machine cycles to perform a computation on a simple machine, a pipeline STALL cycle (also frequently referred to as a "pipeline bubble") must be inserted into the pipeline flow to allow a needed result to propagate through an arithmetic unit. The basic problem therefore is that while pipelining is a valuable concept in a purely throughput-oriented computer system--where the assumption is that computation results are not needed until much, much later--in arithmetic logic units the performance advantage of pipelining or superpipelining techniques is drastically reduced because many computations are latency sensitive.
As will be seen, the present invention makes it possible to improve the performance of a pipelined or superpipelined machine by taking advantage of the redundant intermediate form of a result, even though the full result has not yet completed execution. The redundant form of a result refers to a numerical representation where the particular value being represented has more than one bit pattern encoding. Computer arithmetic and number systems are described generally in the book entitled "Computer Arithmetic Principles, Architecture and Design," by Kih Wang, John Wiley and Sons, 1979, pages 1-12. Redundant representations of numbers are also described generally in pages 97-127 of Mr. Wang's book.